FIG. 1 illustrates a data network comprising a number of network nodes A through Z. The network nodes are interconnected by links for the transmission of data packets and other signals, such as control data, between nodes. Each link of the network connects two neighboring nodes. Preferably each link of the network, in fact, comprises a pair of unidirectional links (dual link segments) and each such pair of links can be realized either by a single communication medium, such as an optical fiber, or by two separate communication mediums, such as a pair of coaxial cables or optical fibers.
Such an organized network structure enables data to be communicated between any pair of nodes including a so-called source node and a so-called target node. The source and target designations are dynamic, varying according to the direction of the traffic, which adds to the complexity of the network architecture.
An optimized network organization, which might in some instances be devoted to control traffic, has already been disclosed in the art. One such organization is referred to as a so-called spanning tree architecture.
FIG. 2 depicts a spanning tree, i.e. an optimal structure, that enables the efficient transmission of a message (e.g. data or control) from any node of the communication network to any other node. The spanning tree contains the links needed to interconnect all nodes without any cycles or loops. The links may be considered as extending outward from one node (e.g. node A in FIG. 2) referred to as the root node. The terminating nodes of the spanning tree (e. g. node F, node G, node K, node L, node N, node Z, node T, node W and node Y) are referred to as leaf nodes. The nodes between the leaf nodes and the root node are referred to as intermediate nodes. It should be noted that, in the structure of the network of FIG. 2, any one of the nodes A through Z might be a root node for a specific spanning representation.
In such a tree structure, the root node is designated through a procedure using both hardware and software means distributed within the network. The links connecting pairs of nodes of the spanning tree are sometimes referred to as "edges".
The root node is also referred to as the parent node of the nodes directly connected to it. All nodes connected directly to the root node are referred to as children nodes of the root node. In an outward progression along the tree structure, each node that is directly connected to another node that is closer to the root node is referred to as the child node of the latter (parent) node. Thus, for instance, with the spanning tree structure shown in FIG. 2, node A is the parent of nodes B, H and M; node B is the parent of node C; node C is the parent of nodes D and G. Conversely nodes D and G are both children nodes of node C. In other words, given a spanning tree structure, the root node is the only node with no parent node. Apart from this characteristic, the root node is not necessarily different from any other node of the spanning tree. Consequently, any one of the nodes A through Z may operate as the root node under certain network conditions.
Obviously, under normal operating conditions, several situations may occur that require reorganization of a spanning tree. For instance a new link may be installed for the purpose of optimizing the flow of network traffic (e.g., a low speed or low capacity link may be replaced by a higher speed or higher capacity link) or to add a new path between nodes. Link replacement should, naturally, be implemented as quickly as possible to avoid network traffic degradation between the time the old link is removed and the new link is available.
If a terminal attached to one node requests access to a CPU (Central Processing Unit) attached to another node, the system should simply and quickly select the path between those two nodes. The faster the path is selected, the better in terms of efficient network operation.
The importance of being able to rapidly reorganize a spanning tree in a modern data network becomes more apparent when it is realized any failure (e.g. link failure) will isolate at least a portion of the tree and completely disrupt the traffic therein, if not in the whole data network.
These situations have already been considered in the prior art but the solutions proposed are not considered fully satisfactory in terms of time required for reorganizing a spanning tree.